{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 21.3 Disjoint-set forests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.3-1\n",
    "\n",
    "> Redo Exercise 21.2-2 using a disjoint-set forest with union by rank and path compression."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.3-2\n",
    "\n",
    "> Write a nonrecursive version of FIND-SET with path compression."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.3-3\n",
    "\n",
    "> Give a sequence of $m$ MAKE-SET, UNION, and FIND-SET operations, $n$ of which are MAKE-SET operations, that takes $\\Omega(m \\lg n)$ time when we use union by rank only."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Omega((m - 2n) \\lg n) = \\Omega(m \\lg n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.3-4\n",
    "\n",
    "> Suppose that we wish to add the operation PRINT-SET$(x)$, which is given a node $x$ and prints all the members of $x$'s set, in any order. Show how we can add just a single attribute to each node in a disjoint-set forest so that PRINT-SET$(x)$ takes time linear in the number of members of $x$'s set and the asymptotic running times of the other operations are unchanged. Assume that we can print each member of the set in $O(1)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each member has a pointer points to the next element in the set, which forms a circular linked list. When union two sets $x$ and $y$, swap $x.next$ and $y.next$ to merged the two linked lists."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.3-5 $\\star$\n",
    "\n",
    "> Show that any sequence of $m$ MAKE-SET, FIND-SET, and LINK operations, where all the LINK operations appear before any of the FIND-SET operations, takes only $O(m)$ time if we use both path compression and union by rank. What happens in the same situation if we use only the path-compression heuristic?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose that there are $n$ MAKE_SET, then after the LINKs, there are only $n$ elements to compress, thus it takes $O(m)$ time. It doesn't matter whether we use union by rank or not."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
